Databases commonly organize data in the form of tables, each table having a number of rows and columns. Each row in a table generally has a data value associated with each of the columns, this intersection of rows and columns commonly called a cell. A system needing access to data in the database typically issues a request in the form of a query. A query usually involves a request for the data contained in one or more cells of any rows which satisfy a particular condition. This condition often involves the comparison of the values of cells in a column to some other value to determine whether the row associated with the compared cell satisfies the condition.
A direct comparison of each cell of interest in a table to a value is often computationally expensive, and database developers have accordingly introduced means by which rows satisfying a comparison operation can be more readily determined without the need to traverse every row of a table. A common improvement involves the use of a tree-based index structure to determine which rows contain a desired value. Each node of the tree represents a distinct value appearing within a particular column in any row of the table. Each node of the tree connects to a data structure representing the set of rows in the table where the indexed column contains the specified distinct value. One such data structure that can be used to represent a set of rows is a bitmap, where each bit with a ‘1’ value within the bitmap corresponds to a row containing the specified distinct value. The rows for which the value of the particular column is satisfied would be represented by “set” bits in the bitmap (i.e., bits set to either a ‘1’ or a ‘0’ value in order to indicate that a corresponding row satisfies the condition or fails to satisfy it).
Bitmap-based conditions are used for accelerating database queries. More specifically bitmaps are used, for example, for restricting evaluation of a disjunct within a disjunction. However, bitmap-based conditions are not used for negated conditions for further accelerating database queries.
In the drawings, like reference numbers generally indicate identical or similar elements. Additionally, generally, the left-most digit(s) of a reference number identifies the drawing in which the reference number first appears.